package leetcode;

public class _1123 {
    /**
     * 最深叶节点的最近公共祖先
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    class Solution {
        private TreeNode ans;
        private int maxDepth = -1;
        public TreeNode lcaDeepestLeaves(TreeNode root) {
            dfs(root,0);
            return ans;
        }
        public int dfs(TreeNode root ,int depth){
            if(root==null){
                maxDepth = Math.max(maxDepth,depth);
                return depth;
            }
            int leftDepth = dfs(root.left,depth+1);
            int rightDepth = dfs(root.right,depth+1);
            if(leftDepth == rightDepth&&leftDepth == maxDepth){
                ans = root;
            }
            return Math.max(leftDepth,rightDepth);
        }
    }
}
